package code.oldCode.feishuSpecializedTraining.binary_tree;

import utils.TreeNode;

import java.util.HashMap;

/**
 * @author 26029
 * @date 2025/3/13
 * @description
 */
public class MyBinaryTree5 {
    // 106. 从中序与后序遍历序列构造二叉树
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int len = inorder.length;
        for (int i = 0; i < len; i++) {
            hashMap.put(inorder[i], i);
        }
        return buildDFS(hashMap, inorder, postorder, 0, len - 1, 0, len - 1);
    }

    public TreeNode buildDFS(HashMap<Integer, Integer> hashMap, int[] inorder, int[] postorder, int beginIn, int endIn, int beginPost, int endPost) {
        if (beginIn > endIn || beginPost > endPost)
            return null;
        // 根据后序最后一个元素找到头节点位置
        int rootPos = hashMap.get(postorder[endPost]);
        // 左：begin~rootPos-1  右：rootPos+1~end
        int leftLen = rootPos - beginIn;
        int rightLen = endIn - rootPos;
        if (leftLen < 0 || rightLen < 0)
            return null;
        TreeNode root = new TreeNode();
        root.val = inorder[rootPos];
        root.left = buildDFS(hashMap, inorder, postorder, beginIn, rootPos - 1, beginPost, beginPost + leftLen - 1);
        root.right = buildDFS(hashMap, inorder, postorder, rootPos + 1, endIn, beginPost + leftLen, endPost - 1);
        return root;
    }

    // 654. 最大二叉树
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0)
            return null;
        return buildMax(nums, 0, nums.length - 1);
    }

    public TreeNode buildMax(int[] nums, int left, int right) {
        if (left > right)
            return null;
        // 找到最大的那个地方
        int maxPos = left;
        int max = nums[left];
        for (int i = left; i <= right; i++) {
            if (nums[i] > max) {
                max = nums[i];
                maxPos = i;
            }
        }
        TreeNode node = new TreeNode();
        node.val = nums[maxPos];
        node.left = buildMax(nums, left, maxPos - 1);
        node.right = buildMax(nums, maxPos + 1, right);
        return node;
    }

    // 617. 合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null)
            return null;
        TreeNode node = new TreeNode();
        if (root1 != null && root2 != null) {
            node.val = root1.val + root2.val;
            node.left = mergeTrees(root1.left, root2.left);
            node.right = mergeTrees(root1.right, root2.right);
        } else if (root1 != null) {
            node.val += root1.val;
            node.left = mergeTrees(root1.left, null);
            node.right = mergeTrees(root1.right, null);
        } else {
            node.val += root2.val;
            node.left = mergeTrees(null, root2.left);
            node.right = mergeTrees(null, root2.right);
        }
        return node;
    }

    // 700. 二叉搜索树中的搜索
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode node = root;
        while (node != null) {
            if (node.val == val)
                return node;
            else if (node.val > val)
                node = node.left;
            else
                node = node.right;
        }
        return null;
    }
}
